/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
// 完全背包问题，超时要进行剪枝
var coinChange = function (coins, amount) {
    let f = new Array(coins.length+1).fill().map((item) => {
        return Array(amount + 1).fill(Infinity)
    })
    f[0][0] = 0
    for (let i = 0; i < coins.length; i++) {
        for (let j = 0; j <= amount; j++) {
            if (j < coins[i]) {
                f[i + 1][j] = f[i][j]
            } else {
                f[i + 1][j] = Math.min(f[i][j], f[i+1][j - coins[i]]+1)
            }
        }
    }
    ans = f[coins.length][amount]
    return ans < Infinity ? ans : -1
};
console.log(coinChange([1, 2, 5], 11));